export const str: string = `<h2 id="冒泡排序">冒泡排序</h2>
<ul>
<li>概念</li>
</ul>
<p>循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。
这样一次循环之后最后一个数就是本数组最大的数。
下一次循环继续上面的操作，不循环已经排序好的数。</p>
<pre><code class="language-javascript">function bubbleSort_V2 (array) {
  for (let i = 0; i &lt; arr.length; i++) {
    for (let j = 0; j &lt; arr.length - 1 - i; j++) {
      if (array[i] &gt; arr[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]]
      }
    }
  }
  return array
}
</code></pre>
<ul>
<li>优化</li>
</ul>
<p>当一次循环没有发生冒泡，说明已经排序完成，停止循环</p>
<pre><code class="language-javascript">function bubbleSort_V2 (array) {
  for (let j = 0; j &lt; array.length; j++) {
    // 判断有没有发生冒泡
    let complete = true
    for (let i = 0; i &lt; array.length - 1 - j; i++) {
      // 比较相邻数
      if (array[i] &gt; array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]]
        complete = false
      }
    }
    // 没有冒泡，结束循环
    if (complete) {
      break
    }
  }
  return array
}
</code></pre>
<ul>
<li>复杂度</li>
</ul>
<p>时间复杂度：<br/> O(n2)</p>
<p>空间复杂度: <br/> O(1)</p>
<h2 id="插入排序">插入排序</h2>
<ul>
<li>概念</li>
</ul>
<p>将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。
插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。</p>
<pre><code class="language-javascript">function insertSort (array) {
  for (let i = 1; i &lt; array.length; i++) {
    for (let j = i - 1; j &gt;= 0; j--) {
      if (array[i] &lt; array[j]) {
        [array[i], array[j]] = [array[j], array[i]]
        i--
      } else {
        // 插入到正确位置了，提前终止
        break
      }
    }
  }
  return array
}
</code></pre>
<ul>
<li>复杂度</li>
</ul>
<p>时间复杂度：<br/>  最好的情况：O(n) <br/> 最差的情况：O(n<em>2) <br/> 平均的情况：O(n</em>2)</p>
<p>空间复杂度: <br/>  O(1)</p>
<ul>
<li>优化</li>
</ul>
<p>利用二分查找法</p>
<pre><code class="language-javascript">function insertSort (array) {
  // 二分查找法 找到插入位置
  const searchInsert = (arr, target, left, right) =&gt; {
    while (left &lt;= right) {
      const mid = Math.ceil(left + (right - left) / 2)
      if (arr[mid] === target) {
        return mid
      } else if (arr[mid] &gt; target) {
        right = mid - 1
      } else if (arr[mid] &lt; target) {
        left = mid + 1
      }
    }
    return left
  }
  for (let i = 1; i &lt; array.length; i++) {
    const idx = searchInsert(array, array[i], 0, i - 1)
    for (let j = idx; j &lt; i; j++) {
      [array[j], array[i]] = [array[i], array[j]]
    }
  }
  return array
}
</code></pre>
<p>复杂度</p>
<p>时间复杂度：<br/>  最好的情况：O(nlogn) <br/>  最差的情况：O(n*2) <br/>  平均的情况：O(nlogn)</p>
<p>空间复杂度: <br/>  O(1)</p>
<h2 id="快速排序">快速排序</h2>
<ul>
<li>概念</li>
</ul>
<p>快速排序实现的重点在于数组的拆分，通常我们将数组的第一个元素定义为比较元素，然后将数组中小于比较元素的数放到左边，将大于比较元素的放到右边，
这样我们就将数组拆分成了左右两部分：小于比较元素的数组；大于比较元素的数组。
我们再对这两个数组进行同样的拆分，直到拆分到不能再拆分，数组就自然而然地以升序排列了。</p>
<pre><code class="language-javascript">function quickSort (arr, l, r) =&gt; {
  if (l &gt;= r) return
  let x = l
  let y = r
  base = arr[l]
  while(x &lt; y) {
    while (x &lt; y &amp;&amp; arr[y] &gt;= base) y--
    if (x &lt; y) arr[x++] = arr[y]
    while (x &lt; y &amp;&amp; arr[x] &lt; base) x++
    if (x &lt; y) arr[y--] = arr[x]
  }
  arr[x] = base
  quickSort(arr, l, x-1)
  quickSort(arr, x+1, r)
  return
}
</code></pre>
<ul>
<li>复杂度</li>
</ul>
<p>时间复杂度：<br/>  平均的情况：O(nlog(n)) <br/> 最差的情况：O(n*2) <br/> </p>
<p>空间复杂度: <br/>  O(n)</p>
<ul>
<li>优化</li>
</ul>
<p>由于递归层数过多可能造成栈溢出
通过单边递归来优化递归层数</p>
<pre><code class="language-javascript">// 左递归法  减少一半的递归层次
function quickSort (arr, l, r) =&gt; {
  while (l &lt; r) {
    let x = l
    let y = r
    base = arr[l]
    while(x &lt; y) {
      while (x &lt; y &amp;&amp; arr[y] &gt;= base) y--
      if (x &lt; y) arr[x++] = arr[y]
      while (x &lt; y &amp;&amp; arr[x] &lt; base) x++
      if (x &lt; y) arr[y--] = arr[x]
    }
    arr[x] = base
    quickSort(arr, x + 1, r)
    r = x - 1
  }
  return
}
</code></pre>
<h2 id="选择排序">选择排序</h2>
<ul>
<li>概念</li>
</ul>
<p>选出最小的一个和第一个位置交换，选出其次小的和第二个位置交换。
直到从第N个和第N-1个元素中选出最小的放在第N-1个位置。</p>
<pre><code class="language-javascript">const selectSort = (arr) =&gt; {
  for (let i = 0; i &lt; arr.length; i++) {
    let min = arr[i]
    for (let j = i + 1; j &lt; arr.length; j++) {
      if (min &gt; arr[j]) {
        const temp = arr[j]
        arr[j] = min
        min = temp
      }
    }
    arr[i] = min
  }
}
</code></pre>
<ul>
<li>复杂度</li>
</ul>
<p>时间复杂度：<br/>  O(n*2) <br/> </p>
<p>空间复杂度: <br/>  O(1)</p>
<h2 id="归并排序">归并排序</h2>
<ul>
<li>概念</li>
</ul>
<p>将数组划分为最长为2的有序子数组。
将两个有序子数组在合并成一个有序数组。
直到合并完所有有序子数组。
返回这个新的有序数组。</p>
<pre><code class="language-javascript">function merge (arr, p, q, r) =&gt;{
  let arr1 = arr.slice(p, q)
  let arr2 = arr.slice(q, r)
  arr1.push(Number.MAX_SAFE_INTEGER)
  arr2.push(Number.MAX_SAFE_INTEGER)
  for (let k = p, i = 0, j = 0; k &lt; r; k++) {
    arr[k] = arr1[i] &lt; arr2[j] ? arr1[i++] : arr2[j++]
  }
}
function mergeSort (arr) =&gt; {
  for (let i = 1; i &lt; arr.length; i++) {
    const step = i * 2
    for (let start = 0; start &lt; arr.length; start += step) {
      const end = Math.min(start + step, arr.length)
      if (end - start &gt; 1) {
        const mid = start + i
        merge(arr, start, mid, end)
      }
    }
  }
}
</code></pre>
<ul>
<li>复杂度</li>
</ul>
<p>时间复杂度：<br/>  O(nlog(n)) <br/> </p>
<p>空间复杂度: <br/>  O(n)</p>
<h2 id="桶排序">桶排序</h2>
<ul>
<li>概念</li>
</ul>
<p>划分多个范围相同的区间，每个子区间自排序，最后合并。</p>
<pre><code class="language-javascript">function insertionSort = (arr) =&gt; {
  for (let i = 1; i &lt; arr.length; i++) {
    let p = i - 1
    const x = arr[p+1]
    while(p &gt;= 0 &amp;&amp; arr[p] &gt; x) {
      arr[p+1] = arr[p]
      p--
    }
    arr[p+1] = x
  }
}
function bucketSort (arr, k, S) =&gt; {
  // 二维数组
  const buckets = arrrray.from({length: k}, () =&gt; [])
  // 放入桶中
  for (let i = 0; i &lt; arr.length; i++) {
    const index = ~~(arr[i] / S)
    buckets[index].push(arr[i])
  }
  // 排序每只桶
  for (let i = 0; i &lt; buckets.length; i++) {
    insertionSort(buckets[i])
  }
  return [].concat(...buckets)
}
</code></pre>
<ul>
<li>复杂度</li>
</ul>
<p>时间复杂度：<br/>  O(n + s) <br/> </p>
<p>空间复杂度: <br/>  O(n + m)</p>
<h2 id="计数排序">计数排序</h2>
<ul>
<li>概念</li>
</ul>
<p>计数排序，不是基于元素比较，而是利用数组下标确定元素的正确位置。
特点：快但是需要知道数组的最大值可能消耗大量空间内存</p>
<pre><code class="language-javascript">// 
function countingSort (arr) =&gt; {
  const max = Math.max(...arr)
  // 累计数组
  const B = Array(max + 1).fill(0)
  // 结果数组
  const C = Array(arr.length)
  // 累计位递增
  arr.forEach((_, i) =&gt; B[arr[i]]++)
  // 累计求和
  for (let i = 1; i &lt; B.length; i++) {
    B[i] = B[i - 1] + B[i]
  }
  // 结果取出
  for (let i = 0; i &lt; arr.length; i++) {
    const p = B[arr[i]] - 1
    B[arr[i]]--
    C[p] = arr[i]
  }
  return C
}
</code></pre>
<ul>
<li>复杂度</li>
</ul>
<p>时间复杂度：<br/>  O(n + k) 其中k是整数的范围 <br/> </p>
<p>空间复杂度: <br/>  O(n + k)</p>
<h2 id="基数排序">基数排序</h2>
<ul>
<li>概念</li>
</ul>
<p>一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。</p>
<pre><code class="language-javascript">// 
function radixSort = (arr) =&gt; {
  const max = Math.max(...arr)
  const buckets = Array.from({ length: 10 }, () =&gt; [])
  // 有效位数
  let m = 1
  while (m &lt; max) {
    // 将数组放入桶中
    arr.forEach(number =&gt; {
      const digit = ~~((number % (m * 10)) / m)
      buckets[digit].push(number)
    })
    // 从桶中取出元素
    let j = 0
    buckets.forEach(bucket =&gt; {
      while(bucket.length &gt; 0) {
        arr[j++] = bucket.shift()
      }
    })
    // 下一个位置
    m *= 10
  }
}
</code></pre>
<ul>
<li>复杂度</li>
</ul>
<p>时间复杂度：<br/>  O(d(n + k)) 其中n表示待排序列的规模，d表示待排序列的最大位数，k表示每一位数的范围 <br/> </p>
<p>空间复杂度: <br/>  O(n + k)</p>
<h2 id="优化版排序">优化版排序</h2>
<ul>
<li>概念</li>
</ul>
<p>基于 C++ 的一种混合快排思想。
快排序 + 堆排序 + 插入排序。
将整个数组分为长度为16的子数组。
子数组排序在和合并。</p>
<pre><code class="language-javascript">// 
const threshold = 16 // 分组
function getMid (arr, a, b , c) =&gt; {
  // 排序选中间的
  // if (a &gt; b) swap(a, b)
  // if (a &gt; c) swap(a, c)
  // if (b &gt; c) swap(b, c)
  if (arr[a] &gt; arr[b]) [arr[a], arr[b]] = [arr[b], arr[a]] 
  if (arr[a] &gt; arr[c]) [arr[a], arr[c]] = [arr[c], arr[a]] 
  if (arr[b] &gt; arr[c]) [arr[b], arr[c]] = [arr[c], arr[b]] 
  return arr[b]
}
// const swap = (arr, l ,mid, r) =&gt; {
// }
function quickSort (arr, l, r) =&gt; {
  while(r - l &gt; threshold) {
    let x = l,
        y = r,
        base = getMid(arr[l], arr[~~((l + r) / 2)], arr[r])
        // base = getMid(arr[l], arr[~~((l + r) / 2)], arr[r])
        base = getMid(arr, l, ~~((l + r) / 2), r)
    do {
      while(arr[x] &lt; base) x++
      while(arr[y] &gt; base) y--
      if (x &lt;= y) {
        [arr[x], arr[y]] = [arr[y], arr[x]]
        // swap(arr[x], arr[y])
        x++
        y--
      } 
    } while (x &lt;= y)
    quickSort(arr, x, r)
    r = y
  }
}
const insertSort = (arr, l, r) =&gt; {
  let ind = l
  for (let i = l + 1; i &lt;= r; i++) {
    if (arr[i] &lt; arr[ind]) ind = i
  }
  while (ind &gt; l) {
    // swap(arr[ind], arr[ind - l])
    [arr[ind], arr[ind - l]] = [arr[ind - l], arr[ind]]
    ind--
  }
  for (let i = l + 2; i &lt;= r; i++) {
    let j = i
    while (arr[j] &lt; arr[j - 1]) {
      // swap(arr[j], arr[j-1])
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]]      
      j--
    }
  }
}
// 最终排序
const finalQuickSort = (arr, l , r) =&gt; {
  quickSort(arr, l ,r)
  insertSort(arr, l ,r)
}
</code></pre>`
